{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Difference of Number of Distinct Values on Diagonals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: differenceOfDistinctValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对角线上不同值的数量差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <code>0</code> 开始、大小为 <code>m x n</code> 的二维矩阵 <code>grid</code> ，请你求解大小同样为 <code>m x n</code> 的答案矩阵 <code>answer</code> 。</p>\n",
    "\n",
    "<p>矩阵 <code>answer</code> 中每个单元格 <code>(r, c)</code> 的值可以按下述方式进行计算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令 <code>topLeft[r][c]</code> 为矩阵 <code>grid</code> 中单元格 <code>(r, c)</code> 左上角对角线上 <strong>不同值</strong> 的数量。</li>\n",
    "\t<li>令 <code>bottomRight[r][c]</code> 为矩阵 <code>grid</code> 中单元格 <code>(r, c)</code> 右下角对角线上 <strong>不同值</strong> 的数量。</li>\n",
    "</ul>\n",
    "\n",
    "<p>然后 <code>answer[r][c] = |topLeft[r][c] - bottomRight[r][c]|</code> 。</p>\n",
    "\n",
    "<p>返回矩阵 <code>answer</code> 。</p>\n",
    "\n",
    "<p><strong>矩阵对角线</strong> 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。</p>\n",
    "\n",
    "<p>如果单元格 <code>(r1, c1)</code> 和单元格 <code>(r, c) </code>属于同一条对角线且 <code>r1 &lt; r</code> ，则单元格 <code>(r1, c1)</code> 属于单元格 <code>(r, c)</code> 的左上对角线。类似地，可以定义右下对角线。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/19/ex2.png\" style=\"width: 786px; height: 121px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,3],[3,1,5],[3,2,1]]\n",
    "<strong>输出：</strong>[[1,1,0],[1,0,1],[0,1,1]]\n",
    "<strong>解释：</strong>第 1 个图表示最初的矩阵 grid 。&nbsp;\n",
    "第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。\n",
    "第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。\n",
    "第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。\n",
    "- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。\n",
    "- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。\n",
    "- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。\n",
    "其他单元格的对应答案也可以按照这样的流程进行计算。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1]]\n",
    "<strong>输出：</strong>[[0]]\n",
    "<strong>解释：</strong>- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n, grid[i][j] &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [difference-of-number-of-distinct-values-on-diagonals](https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [difference-of-number-of-distinct-values-on-diagonals](https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[3,1,5],[3,2,1]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      result = [[0] * n for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          topLeft = []\n",
    "          topLeftNums = 0\n",
    "          for k in range(min(i, j)):\n",
    "            if not grid[i-k-1][j-k-1] in topLeft:\n",
    "              topLeftNums += 1\n",
    "              topLeft.append(grid[i-k-1][j-k-1])\n",
    "          topLeft = []\n",
    "          for k in range(min(m - i - 1, n - j - 1)):\n",
    "            if not grid[i+k+1][j+k+1] in topLeft:\n",
    "              topLeftNums -= 1\n",
    "              topLeft.append(grid[i+k+1][j+k+1])\n",
    "          result[i][j] = abs(topLeftNums)\n",
    "        \n",
    "      return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(0,m):\n",
    "            res.append([0]*n)\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                s1 = set()\n",
    "                s2 = set()\n",
    "\n",
    "                temp_i = i - 1\n",
    "                temp_j = j - 1\n",
    "                while temp_i >= 0 and temp_j >= 0:\n",
    "                    s1.add(grid[temp_i][temp_j])\n",
    "                    temp_i -= 1\n",
    "                    temp_j -= 1\n",
    "                \n",
    "                temp_i = i + 1\n",
    "                temp_j = j + 1\n",
    "                while temp_i < m and temp_j < n:\n",
    "                    s2.add(grid[temp_i][temp_j])\n",
    "                    temp_i += 1\n",
    "                    temp_j += 1\n",
    "                #print(i,j)\n",
    "                #print(s1)\n",
    "                #print(s2)\n",
    "                res[i][j] = abs(len(s1)-len(s2))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s=set()\n",
    "                x,y=i-1,j-1\n",
    "                while x>=0 and y>=0:\n",
    "                    s.add(grid[x][y])\n",
    "                    x-=1\n",
    "                    y-=1\n",
    "                st=len(s)\n",
    "                s.clear()\n",
    "                x,y=i+1,j+1\n",
    "                while x<m and y<n:\n",
    "                    s.add(grid[x][y])\n",
    "                    x+=1\n",
    "                    y+=1\n",
    "                res[i][j]=abs(st-len(s))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        res=[[0]*m for _ in range(n)]\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,m):\n",
    "                x,y=set(),set()\n",
    "                for k in range(1,min(n-i,m-j)):\n",
    "                    x.add(grid[i+k][j+k])\n",
    "                for k in range(1,min(i,j)+1):\n",
    "                    y.add(grid[i-k][j-k])\n",
    "                res[i][j]=abs(len(x)-len(y))\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        line_value = defaultdict(list)\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                line_value[j - i].append(grid[i][j])\n",
    "        \n",
    "        result = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i <= j:\n",
    "                    result[i][j] = abs(len(set(line_value[j - i][i+1:])) - len(set(line_value[j - i][:i])))\n",
    "                else:\n",
    "                    result[i][j] = abs(len(set(line_value[j - i][j+1:])) - len(set(line_value[j - i][:j])))\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        ans=[[0]*m for _ in range(n)]\n",
    "        for y in range(n):\n",
    "            for x in range(m):\n",
    "                top,bottom=set(),set()\n",
    "                for i in range(1,min(x,y)+1):\n",
    "                    top.add(grid[y-i][x-i])\n",
    "                for i in range(1,min(m-x,n-y)):\n",
    "                    bottom.add(grid[y+i][x+i])\n",
    "                ans[y][x]=abs(len(top)-len(bottom))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(n - k, 0)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "\n",
    "            s.clear()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def get_ans(x, y):\n",
    "            top_left = []\n",
    "            button_right = []\n",
    "            now_x = x-1\n",
    "            now_y = y-1\n",
    "            while now_x > -1 and now_y > -1:\n",
    "                top_left.append(grid[now_x][now_y])\n",
    "                now_x -= 1\n",
    "                now_y -= 1\n",
    "            now_x = x + 1\n",
    "            now_y = y + 1\n",
    "            while now_x < m and now_y < n:\n",
    "                button_right.append(grid[now_x][now_y])\n",
    "                now_x += 1\n",
    "                now_y += 1\n",
    "            return abs(len(list(set(top_left))) - len(list(set(button_right))))\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get_ans(i, j)\n",
    "        return ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        ans = [[0] * c for _ in range(r)]\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                topleft = set()\n",
    "                botright = set()\n",
    "\n",
    "                x = i - 1\n",
    "                y = j - 1\n",
    "\n",
    "                while x >= 0 and y >= 0:\n",
    "                    topleft.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "\n",
    "                \n",
    "                x = i + 1\n",
    "                y = j + 1\n",
    "\n",
    "                while x < r and y < c:\n",
    "                    botright.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "\n",
    "\n",
    "                ans[i][j] = abs(len(topleft) - len(botright))\n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # topLeft\n",
    "                s = set()\n",
    "                x, y = i - 1, j - 1\n",
    "                while x >= 0 and y >= 0:\n",
    "                    s.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                sz = len(s)\n",
    "\n",
    "                # bottomRight\n",
    "                s.clear()\n",
    "                x, y = i + 1, j + 1\n",
    "                while x < m and y < n:\n",
    "                    s.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                ans[i][j] = abs(sz - len(s))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [[0 for i in range(n)]for i in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            nums = []\n",
    "            x = i\n",
    "            y = 0\n",
    "            while(x < m and y < n):\n",
    "                nums.append(grid[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            x = i\n",
    "            y = 0\n",
    "            j = 0\n",
    "            while(j < len(nums)):\n",
    "                len1 = len(set(nums[:j]))\n",
    "                len2 = len(set(nums[j+1:]))\n",
    "                ans[x][y] = abs(len1-len2)\n",
    "                j += 1\n",
    "                x += 1\n",
    "                y += 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            nums = []\n",
    "            x = 0\n",
    "            y = i\n",
    "            while(x < m and y < n):\n",
    "                nums.append(grid[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            x = 0\n",
    "            y = i\n",
    "            j = 0\n",
    "            while(j < len(nums)):\n",
    "                len1 = len(set(nums[:j]))\n",
    "                len2 = len(set(nums[j+1:]))\n",
    "                ans[x][y] = abs(len1-len2)\n",
    "                j += 1\n",
    "                x += 1\n",
    "                y += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ret = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = 0\n",
    "                s = set()\n",
    "                while True:\n",
    "                    k += 1\n",
    "                    if i - k >= 0 and j - k >= 0:\n",
    "                        s.add(grid[i - k][j - k])\n",
    "                    else:\n",
    "                        break\n",
    "                k = 0\n",
    "                s2 = set()\n",
    "                while True:\n",
    "                    k += 1\n",
    "                    if i + k < m and j + k < n:\n",
    "                        s2.add(grid[i + k][j + k])\n",
    "                    else:\n",
    "                        break\n",
    "                ret[i][j] = abs(len(s)  - len(s2))\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(n - k, 0)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "            s.clear()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      result = [[0] * n for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          topLeft = []\n",
    "          bottomRight = []\n",
    "          topLeftNums = 0\n",
    "          bottomRightNums = 0\n",
    "          for k in range(min(i, j)):\n",
    "            if not grid[i-k-1][j-k-1] in topLeft:\n",
    "              topLeftNums += 1\n",
    "              topLeft.append(grid[i-k-1][j-k-1])\n",
    "          for k in range(min(m - i - 1, n - j - 1)):\n",
    "            if not grid[i+k+1][j+k+1] in bottomRight:\n",
    "              bottomRightNums += 1\n",
    "              bottomRight.append(grid[i+k+1][j+k+1])\n",
    "          result[i][j] = abs(topLeftNums - bottomRightNums)\n",
    "        \n",
    "      return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # topLeft\n",
    "                s = set()\n",
    "                x, y = i - 1, j - 1\n",
    "                while x >= 0 and y >= 0:\n",
    "                    s.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                sz = len(s)\n",
    "\n",
    "                # bottomRight\n",
    "                s.clear()\n",
    "                x, y = i + 1, j + 1\n",
    "                while x < m and y < n:\n",
    "                    s.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                ans[i][j] = abs(sz - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        res=[[0]*m for _ in range(n)]\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,m):\n",
    "                x,y=set(),set()\n",
    "                # while k1<n and k2<m:\n",
    "                #     x.add(grid[k1][k2])\n",
    "                #     k1+=1\n",
    "                #     k2+=1\n",
    "                for k in range(1,min(n-i,m-j)):\n",
    "                    x.add(grid[i+k][j+k])\n",
    "                for k in range(1,min(i,j)+1):\n",
    "                    y.add(grid[i-k][j-k])\n",
    "                res[i][j]=abs(len(x)-len(y))\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        a = [1] * 51\n",
    "        # d = c - r\n",
    "        for d in range(1-m, n):\n",
    "            s = 0\n",
    "            for r in range(max(0, -d), min(m, n - d)):\n",
    "                c = r + d\n",
    "                res[r][c] = s\n",
    "                x = grid[r][c]\n",
    "                s += a[x]\n",
    "                a[x] = 0\n",
    "            for r in range(max(0, -d), min(m, n - d)):\n",
    "                a[grid[r][r+d]] = 1\n",
    "        for d in range(1-m, n):\n",
    "            s = 0\n",
    "            for r in reversed(range(max(0, -d), min(m, n - d))):\n",
    "                c = r + d\n",
    "                res[r][c] = abs(res[r][c] - s)\n",
    "                x = grid[r][c]\n",
    "                s += a[x]\n",
    "                a[x] = 0\n",
    "            for r in range(max(0, -d), min(m, n - d)):\n",
    "                a[grid[r][r+d]] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      result = [[0 for _ in range(n)] for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          topLeft = []\n",
    "          bottomRight = []\n",
    "          topLeftNums = 0\n",
    "          bottomRightNums = 0\n",
    "          for k in range(min(i, j)):\n",
    "            if not grid[i-k-1][j-k-1] in topLeft:\n",
    "              topLeftNums += 1\n",
    "              topLeft.append(grid[i-k-1][j-k-1])\n",
    "          for l in range(min(m - i - 1, n - j - 1)):\n",
    "            if not grid[i+l+1][j+l+1] in bottomRight:\n",
    "              bottomRightNums += 1\n",
    "              bottomRight.append(grid[i+l+1][j+l+1])\n",
    "          result[i][j] = abs(topLeftNums - bottomRightNums)\n",
    "        \n",
    "      return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ans = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                l = set()\n",
    "                r = set()\n",
    "                x,y = i-1,j-1\n",
    "                while x >= 0 and y >= 0:\n",
    "                    l.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                x,y = i+1,j+1\n",
    "                while x < n and y < m:\n",
    "                    r.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                ans[i][j] = abs(len(l)-len(r))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        ans = [[0] * n for _ in range(m)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                st1, st2 = set(), set()\r\n",
    "                #计算左上角对角线上不同值的数量\r\n",
    "                l_i, l_j = i-1, j-1\r\n",
    "                while l_i >= 0 and l_j >= 0:\r\n",
    "                    st1.add(grid[l_i][l_j])\r\n",
    "                    l_i -= 1\r\n",
    "                    l_j -= 1\r\n",
    "                #计算右下角对角线上不同值的数量\r\n",
    "                r_i, r_j = i+1, j+1\r\n",
    "                while r_i < m and r_j < n:\r\n",
    "                    st2.add(grid[r_i][r_j])\r\n",
    "                    r_i += 1\r\n",
    "                    r_j += 1\r\n",
    "                ans[i][j] = abs(len(st1) - len(st2))\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(n - k, 0)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "            s.clear()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ans = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                s1 = set()\n",
    "                s2 = set()\n",
    "                for a in range(-min(i, j), min(n-i, m-j)):\n",
    "                    if a < 0:\n",
    "                        s1.add(grid[i+a][j+a])\n",
    "                    elif a > 0:\n",
    "                        s2.add(grid[i+a][j+a])\n",
    "                ans[i][j] = abs(len(s1) - len(s2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      result = [[0] * n for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          topLeft = []\n",
    "          bottomRight = []\n",
    "          topLeftNums = 0\n",
    "          bottomRightNums = 0\n",
    "          for k in range(min(i, j)):\n",
    "            if not grid[i-k-1][j-k-1] in topLeft:\n",
    "              topLeftNums += 1\n",
    "              topLeft.append(grid[i-k-1][j-k-1])\n",
    "          for k in range(min(m - i - 1, n - j - 1)):\n",
    "            if not grid[i+k+1][j+k+1] in bottomRight:\n",
    "              bottomRightNums += 1\n",
    "              bottomRight.append(grid[i+k+1][j+k+1])\n",
    "          result[i][j] = abs(topLeftNums - bottomRightNums)\n",
    "        \n",
    "      return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos_2_values = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos_2_values[j - i].append(grid[i][j])\n",
    "        pos_2_index = defaultdict(int)\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos = j - i\n",
    "                index = pos_2_index[pos]\n",
    "                arr = pos_2_values[pos]\n",
    "                ans[i][j] = abs(len(set(arr[:index])) - len(set(arr[index + 1:])))\n",
    "                pos_2_index[pos] += 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0]*n for t in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 右下\n",
    "                x, y = i+1, j+1\n",
    "                setr = set()\n",
    "                while x<m and y<n:\n",
    "                    setr.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                # 左上\n",
    "                x, y = i-1, j-1\n",
    "                setl = set()\n",
    "                while x>=0 and y>=0:\n",
    "                    setl.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                ans[i][j] = abs(len(setl) - len(setr))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(n - k, 0)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "            # topLeft\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "            # bottomRight\n",
    "            s.clear()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(0, n - k)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "            s = set()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "      m = len(grid)\n",
    "      n = len(grid[0])\n",
    "      result = [[0 for i in range(n)] for j in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          topLeft = []\n",
    "          bottomRight = []\n",
    "          topLeftNums = 0\n",
    "          bottomRightNums = 0\n",
    "          for k in range(min(i, j)):\n",
    "            if not grid[i-k-1][j-k-1] in topLeft:\n",
    "              topLeftNums += 1\n",
    "              topLeft.append(grid[i-k-1][j-k-1])\n",
    "          for l in range(min(m - i - 1, n - j - 1)):\n",
    "            if not grid[i+l+1][j+l+1] in bottomRight:\n",
    "              bottomRightNums += 1\n",
    "              bottomRight.append(grid[i+l+1][j+l+1])\n",
    "          result[i][j] = abs(topLeftNums - bottomRightNums)\n",
    "        \n",
    "      return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * n for _ in range(m)]\n",
    "        right = [[0] * n for _ in range(m)]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            j = 0\n",
    "            sett = set()\n",
    "            while i < m and j < n:\n",
    "                left[i][j] = len(sett)\n",
    "                sett.add(grid[i][j])\n",
    "                i += 1\n",
    "                j += 1\n",
    "        for j in range(1, n):\n",
    "            i = 0\n",
    "            sett = set()\n",
    "            while i < m and j < n:\n",
    "                left[i][j] = len(sett)\n",
    "                sett.add(grid[i][j])\n",
    "                i += 1\n",
    "                j += 1\n",
    "        for i in range(m):\n",
    "            j = n - 1\n",
    "            sett = set()\n",
    "            while i >= 0 and j >= 0:\n",
    "                right[i][j] = len(sett)\n",
    "                sett.add(grid[i][j])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "        for j in range(n-1):\n",
    "            i = m - 1\n",
    "            sett = set()\n",
    "            while i >= 0 and j >= 0:\n",
    "                right[i][j] = len(sett)\n",
    "                sett.add(grid[i][j])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = abs(left[i][j] - right[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in  range(m):\n",
    "            for j in range(n):\n",
    "                # 计算上半部分\n",
    "                top = []\n",
    "                a = i - 1\n",
    "                b = j - 1\n",
    "                while  a>=0 and b>=0:\n",
    "                    if grid[a][b] not in top:\n",
    "                        top.append(grid[a][b])\n",
    "                    a-=1\n",
    "                    b-=1\n",
    "                # 计算下半部分\n",
    "                bottom = []\n",
    "                a = i + 1\n",
    "                b = j + 1\n",
    "                while a < m and b < n:\n",
    "                    if grid[a][b] not in bottom:\n",
    "                        bottom.append(grid[a][b])\n",
    "                    a+=1\n",
    "                    b+=1\n",
    "                \n",
    "                ans[i][j] = abs(len(top)- len(bottom))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for k in range(1, m + n):\n",
    "            min_j = max(n - k, 0)\n",
    "            max_j = min(m + n - 1 - k, n - 1)\n",
    "            # topLeft\n",
    "            s = set()\n",
    "            for j in range(min_j, max_j):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i + 1][j + 1] = len(s)\n",
    "            # bottomRight\n",
    "            s.clear()\n",
    "            for j in range(max_j, min_j, -1):\n",
    "                i = k + j - n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # topLeft\n",
    "                s = set()\n",
    "                x, y = i - 1, j - 1\n",
    "                while x >= 0 and y >= 0:\n",
    "                    s.add(grid[x][y])\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                sz = len(s)\n",
    "\n",
    "                # bottomRight\n",
    "                s.clear()\n",
    "                x, y = i + 1, j + 1\n",
    "                while x < m and y < n:\n",
    "                    s.add(grid[x][y])\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                ans[i][j] = abs(sz - len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        res=[[0]*m for _ in range(n)]\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,m):\n",
    "                x,y=set(),set()\n",
    "                k1,k2=i+1,j+1\n",
    "                while k1<n and k2<m:\n",
    "                    x.add(grid[k1][k2])\n",
    "                    k1+=1\n",
    "                    k2+=1\n",
    "                # for k in range(1,min(n,m)-max(i,j)):\n",
    "                #     x.add(grid[i+k][j+k])\n",
    "                k1,k2=i-1,j-1\n",
    "                while k1>=0 and k2>=0:\n",
    "                    y.add(grid[k1][k2])\n",
    "                    k1-=1\n",
    "                    k2-=1\n",
    "                res[i][j]=abs(len(x)-len(y))\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_top_left(grid:List[List[int]], m, n):\n",
    "    check_list = []\n",
    "    m -= 1\n",
    "    n -= 1\n",
    "    while m >=0 and n >=0:\n",
    "        if grid[m][n] not in check_list:\n",
    "            check_list.append(grid[m][n])\n",
    "        m -= 1\n",
    "        n -= 1\n",
    "    return len(check_list)\n",
    "\n",
    "def get_bottom_right(grid:List[List[int]], m, n):\n",
    "    check_list = []\n",
    "    l_col = len(grid)\n",
    "    l_line = len(grid[0])\n",
    "    m += 1\n",
    "    n += 1\n",
    "    while m < l_col and n < l_line:\n",
    "        if grid[m][n] not in check_list:\n",
    "            check_list.append(grid[m][n])\n",
    "        m += 1\n",
    "        n += 1\n",
    "    return len(check_list)\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        tmp = [0] * len(grid[0])\n",
    "        tmp_1 = []\n",
    "        for i in range(len(grid)):\n",
    "            tmp_1.append(tmp.copy())\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                tmp_1[i][j] = abs(get_bottom_right(grid, i, j) - get_top_left(grid, i, j))\n",
    "        return tmp_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s = 0\n",
    "                ni, nj = i, j\n",
    "                while 0 <= (ni := ni - 1) < m and 0 <= (nj := nj - 1) < n:\n",
    "                    s |= 1 << grid[ni][nj]\n",
    "                \n",
    "                s2 = 0\n",
    "                ni, nj = i, j\n",
    "                while 0 <= (ni := ni + 1) < m and 0 <= (nj := nj + 1) < n:\n",
    "                    s2 |= 1 << grid[ni][nj]\n",
    "                \n",
    "                ans[i][j] = abs(s.bit_count() - s2.bit_count())\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        answer=[[0]*n for _ in range(m)]\n",
    "        def lcount(r,c):\n",
    "            st=set()\n",
    "            while r-1 >= 0 and c-1 >= 0:\n",
    "                st.add(grid[r-1][c-1])\n",
    "                r -= 1\n",
    "                c -= 1\n",
    "            return len(st)\n",
    "        def rcount(r,c):\n",
    "            st=set()\n",
    "            while r+1 <= m-1 and c+1 <= n-1:\n",
    "                st.add(grid[r+1][c+1])\n",
    "                r += 1\n",
    "                c += 1\n",
    "            return len(st)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                answer[i][j] = abs(lcount(i,j)-rcount(i,j))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        left_up, right_down = defaultdict(set), defaultdict(set)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        # 从左上到右下\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                pos = y - x\n",
    "                ans[x][y] = len(left_up[pos])\n",
    "                left_up[pos].add(grid[x][y])\n",
    "        # 从右下到左上\n",
    "        for x in range(m - 1, -1, -1):\n",
    "            for y in range(n - 1, -1, -1):\n",
    "                pos = y - x\n",
    "                ans[x][y] = abs(ans[x][y] - len(right_down[pos]))\n",
    "                right_down[pos].add(grid[x][y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for k in range(1,m+n):\n",
    "            min_j = max(n-k,0)\n",
    "            max_j = min(n+m-1-k,n-1)\n",
    "            s =set()\n",
    "\n",
    "            for j in range(min_j,max_j):\n",
    "                i =k+j-n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i+1][j+1] =len(s)\n",
    "            \n",
    "            s.clear()\n",
    "            for j in range(max_j,min_j,-1):\n",
    "                i =k+j-n\n",
    "                s.add(grid[i][j])\n",
    "                ans[i-1][j-1] = abs(ans[i-1][j-1]-len(s))\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(g),len(g[0])\n",
    "        ans=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s1,s2=set(),set()\n",
    "                r=-1\n",
    "                while i+r>=0 and j+r>=0:\n",
    "                    s1.add(g[i+r][j+r])\n",
    "                    r-=1\n",
    "                r=1\n",
    "                while i+r<m and j+r<n:\n",
    "                    s2.add(g[i+r][j+r])\n",
    "                    r+=1\n",
    "                ans[i][j]=abs(len(s1)-len(s2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        answer = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                topLeft = set()\n",
    "                bottomRight = set()\n",
    "                i, j = r, c\n",
    "\n",
    "                while i >= 0 and j >= 0:\n",
    "                    topLeft.add(grid[i][j])\n",
    "                    i -= 1\n",
    "                    j -= 1\n",
    "\n",
    "                i, j = r, c\n",
    "                while i < m and j < n:\n",
    "                    bottomRight.add(grid[i][j])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "\n",
    "                i, j = r - 1, c + 1\n",
    "                while i >= 0 and j < n:\n",
    "                    topLeft.add(grid[i][j])\n",
    "                    i -= 1\n",
    "                    j += 1\n",
    "\n",
    "                i, j = r + 1, c - 1\n",
    "                while i < m and j >= 0:\n",
    "                    bottomRight.add(grid[i][j])\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "\n",
    "                topLeft = topLeft.intersection(set(grid[i][j] for i, j in zip(range(r - 1, -1, -1), range(c - 1, -1, -1))))\n",
    "                bottomRight = bottomRight.intersection(set(grid[i][j] for i, j in zip(range(r + 1, m), range(c + 1, n))))\n",
    "\n",
    "                answer[r][c] = abs(len(topLeft) - len(bottomRight))\n",
    "\n",
    "        return answer"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
